﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Allocation
{
    public class ResourceAllocationSolver
    {
        private readonly Func<IMap<Tuple<int, int>, double>> _createMap;

        public ResourceAllocationSolver(Func<IMap<Tuple<int,int>,double>> createMap = null)
        {
            _createMap = createMap ?? (() => AlgoritmiaFactory.Maps<Tuple<int, int>, double>.Default);
        }

        public double Profit(int U, IList<int> maximums, IMap<Tuple<int,int>,double> values )
        {
            var N = maximums.Count;
            var p = _createMap();
            for(var u = 0; u <= U; u++)
            {
                p[new Tuple<int, int>(0, u)] = 0.0;
            }
            for (var n = 1; n <= N; n++)
            {
                p[new Tuple<int, int>(n, 0)] = 0.0;
                for(var u = 1; u <= U; u++)
                {
                    p[new Tuple<int, int>(n, u)] =
                        Enumerable.Range(0, Math.Min(u, maximums[n-1]) + 1).Select(
                            k => p[new Tuple<int, int>(n - 1,u -k )] + values[new Tuple<int, int>(n - 1, k)]).Max();
                }
            }
            return p[new Tuple<int, int>(N, U)];
        }
    }
}
